package main

import (
	"fmt"
)

var Gmap = make(map[int64]int64)

// fibMapNoRecursion 斐波那契数列----使用map版
func fibMap(n int64) int64 {
	if n < 0 {
		panic("不能小于0")
	}
	if n < 3 {
		return Gmap[n]
	}
	Gmap[n] = Gmap[n-1] + Gmap[n-2]
	return Gmap[n]
}

// 1、递推公式
var MapRecursion = make(map[int64]int64)

// fibMapRecursion 斐波那契数列----使用map递归版
func fibMapRecursion(n int64) int64 {
	switch {
	case n < 0:
		panic("不能小于0")
	case n == 0 || n == 1:
		MapRecursion[n] = n
		return MapRecursion[n]
	}

	if _, ok := MapRecursion[n]; !ok {
		MapRecursion[n] = fibMapRecursion(n-1) + MapRecursion[n-2]
	}
	return MapRecursion[n]
}

func main() {
	// 第3题 分析斐波那契数列递推公式递归版本的问题，试着为该函数提供一个Cache，使其计算效率提升
	Gmap[0] = 0
	Gmap[1] = 1
	Gmap[2] = 1
	for i := 0; i <= 80; i++ {
		fibMap(int64(i))
		fibMapRecursion(int64(i))
	}
	fmt.Println(Gmap)
	fmt.Println("~~~~~~~~~~~~~~")
	fmt.Println(MapRecursion)
}
